//存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。 
//
// 给定一个二维数组 graph ，表示图，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v 
//，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性： 
//
// 
// 不存在自环（graph[u] 不包含 u）。 
// 不存在平行边（graph[u] 不包含重复值）。 
// 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图） 
// 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。 
// 
//
// 二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称
//为 二分图 。 
//
// 如果图是二分图，返回 true ；否则，返回 false 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
//输出：false
//解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。 
//
// 示例 2： 
//
// 
//
// 
//输入：graph = [[1,3],[0,2],[1,3],[0,2]]
//输出：true
//解释：可以将节点分成两组: {0, 2} 和 {1, 3} 。 
//
// 
//
// 提示： 
//
// 
// graph.length == n 
// 1 <= n <= 100 
// 0 <= graph[u].length < n 
// 0 <= graph[u][i] <= n - 1 
// graph[u] 不会包含 u 
// graph[u] 的所有值 互不相同 
// 如果 graph[u] 包含 v，那么 graph[v] 也会包含 u 
// 
//
// 
//
// 
// 注意：本题与主站 785 题相同： https://leetcode-cn.com/problems/is-graph-bipartite/ 
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 图 👍 61 👎 0


package LeetCode.editor.cn;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

/**
 * @author ldltd
 * @date 2025-04-02 22:17:46
 * @description LCR 106.判断二分图
 */
public class VEAB3K{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 VEAB3K fun=new VEAB3K();
	 	 Solution solution = fun.new Solution();
		  int a=1;
		 System.out.println(-a);
		 System.out.println(-(-a));
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 /*1、深度优先搜索 / 广度优先搜索
我们使用图搜索算法从各个连通域的任一顶点开始遍历整个连通域，
遍历的过程中用两种不同的颜色对顶点进行染色，相邻顶点染成相反的颜色。
这个过程中倘若发现相邻的顶点被染成了相同的颜色，说明它不是二分图；
反之，如果所有的连通域都染色成功，说明它是二分图。

2、并查集
我们知道如果是二分图的话，那么图中每个顶点的所有邻接点都应该属于同一集合，
且不与顶点处于同一集合。因此我们可以使用并查集来解决这个问题，我们遍历图中每个顶点，
将当前顶点的所有邻接点进行合并，
并判断这些邻接点中是否存在某一邻接点已经和当前顶点处于同一个集合中了，若是，则说明不是二分图。
*/
	//bfs
    public boolean isBipartite2(int[][] graph) {
		int n = graph.length;
		int[] vis = new int[n]; // 0:未访问, 1:组1, -1:组2
		Queue<Integer> q = new ArrayDeque<>();
		for (int i = 0; i < n; i++) {
			if (vis[i] != 0) continue; // 已访问过
			q.offer(i);
			vis[i] = 1;
			while (!q.isEmpty()) {
				int node = q.poll();
				for (int neighbor : graph[node]) {
					if (vis[neighbor] == 0) {
						vis[neighbor] = -vis[node];
						q.offer(neighbor);
					} else if (vis[neighbor] == vis[node]) {
						return false;
					}
				}
			}
		}
		return true;
	}
	//dfs
	int [] vis;
	public boolean isBipartite1(int[][] graph) {
		vis = new int[graph.length];
		for (int i = 0; i < graph.length; i++) {
			if (vis[i] == 0) {
				vis[i] = 1;
				if (!dfs(i, graph)) {
					return false;
				}
			}
		}
		return true;
	}
	private boolean dfs(int node, int[][] graph) {
		for (int neighbor : graph[node]) {
			if (vis[neighbor] == 0) {
				vis[neighbor] = -vis[node];
				if (!dfs(neighbor, graph)) {
					return false;
				}
			} else if (vis[neighbor] == vis[node]) {
				return false;
			}
		}
		return true;
	}

	public boolean isBipartite(int[][] graph) {
		unionFind uf=new unionFind(graph.length);

		for (int i = 0; i < graph.length; i++) {
			for (int w : graph[i]) {
				//如果某个临界点与当前顶点已经在一个集合了，说明不是二分图，false
				if(uf.isConnected(i,w)) return false;
				//把所有的邻接点放到一个集合中
				uf.union(graph[i][0],w);
			}
		}
		return true;
	}

	class unionFind{
		int [] roots;
		public unionFind(int n){
			roots=new int[n];
			//初始化每个节点的父节点就是自己
			for (int i = 0; i < n; i++) {
				roots[i]=i;
			}
		}
		public int find(int i){
			if(roots[i]==i) return i;
			return roots[i]=find(roots[i]);
		}
		public boolean isConnected(int p,int q){
			return find(q)==find(p);
		}
		public void union(int p,int q){
			roots[find(q)]=find(p);
		}

	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
